Prefix Output:

Getting the Prefix Output

Preorder Traversal

With the tree built, we traverse it in Preorder to get the prefix expression. The rule is simple and recursive: (1) Visit Root, (2) Traverse Left, (3) Traverse Right.

Click "Next Step" to begin the traversal.

def preorder_traversal(node):
    if not node: return []
    
    # Combine Root, Left, and Right sub-trees
    return [node.value] + \
           preorder_traversal(node.left) + \
           preorder_traversal(node.right)